package hot100;

import java.util.List;

public class ListSort {

}

class ListQuickSort {

    public void quickSort(ListNode head, ListNode tail) {
        if (head == tail) {
            return;
        }
        ListNode smallPrev = head;
        ListNode small = head;
        ListNode pPrev = head;
        ListNode p = pPrev.next;
        while (p != tail) {
            if (p.val < head.val) {
                smallPrev = small;
                small = small.next;
                if (small != p) {
                    ListNode tmp = p.next;
                    smallPrev.next = p;
                    p.next = small.next;
                    pPrev.next = small;
                    small.next = tmp;
                }
            }
            pPrev = p;
            p = p.next;
        }
        smallPrev = small;
        small = small.next;
        if (small != head) {
            ListNode tmp = small.next;
            small.next = head.next;
            smallPrev.next = head;
            head.next = tmp;
        }
        quickSort(head, smallPrev);
        quickSort(smallPrev.next, tail);

    }

}
